The present invention relates to a method and apparatus for adaptively and dynamically representing multidimensional data using view element sets that can be used to construct aggregated and segmented views of the data.
In applications involving online analytical processing (OLAP), image storage and retrieval (ISandT), geographic information systems (GIS) and video-on demand (VOD) systems, it is necessary to provide fast access to views of the data that involve various aggregations and segmentations of the data. To illustrate, an example aggregated and segmented view of a two-dimensional digital image corresponds to a spatial portion of a reduced-resolution version of the image. By pre-aggregating, partitioning and indexing the data accordingly, it is possible to provide more direct access to the data views of interest.
Data partitioning has been utilized in the context of database systems for the declustering and fragmentation of relational data tables to better allocate the data to sites in a communication network. In applications involving digital imagery, data partitioning in the form of quadtree segmentation has been used to split two-dimensional image data into spatial partitions, which can be stored separately or indexed as distinct units. By partitioning the data, views which comprise only portions of the full data set are more readily retrieved and assembled from the partitions.
Alternatively, the data views of interest may involve aggregations that compute averages from the data or that reduce the resolution of the data, such as thumbnail images providing reduced-resolution views of corresponding larger images. Data partitioning using filter banks has been used to split two-dimensional image data into spectral partitions, which correspond to aggregated and residual views of the images.
Aggregations of relational data involving combinations of multiple attributes can be represented using data cubes. The aggregated views of the data correspond to the cells of the data cube. By arranging the views in the data cube into a dependency hierarchy, it is possible to materialize, or precompute and store, only a subset of the views, and to compute additional views from the materialized views, as taught in H. Gupta, V. Harinarayan, A. Rajaraman and J. D. Ullman, Index Selection for OLAP,xe2x80x9d Proc. of the 13th Int""l Conf. on Data Engineering, 1997.
In the past, multiple-resolution views of images have been organized into redundant and non-redundant pyramidal forms to allow reduced-resolution views of the data to be accessed. The multidimensional data can be jointly aggregated and spatially partitioned. Data decompositions involving segmentation and aggregation of multidimensional lattice data have been developed in the Double-tree (see: C. Herley, J. Kovacevic, K. Ramchandran, and M. Vetterli, xe2x80x9cTilings of the Time-Frequency Plane: Constructions of Arbitrary Orthogonal Bases and Fast Tiling Algorithms, xe2x80x9d IEEE Trans. on Image Processing, December, 1993), Dual Double-tree (see: J. R. Smith and S. -F. Chang, xe2x80x9cFrequency and Spatially Adaptive Wavelet Packets,xe2x80x9d Proc. IEEE ICASSP, May, 1995), JASF Graph, and Space-Frequency Tree (see: J. R. Smith and S. -F. Chang, xe2x80x9cJoint Adaptive Space and Frequency Graph Basis Selection,xe2x80x9d Proc. IEEE ICIP, October 1997).
There can be benefit to making a good selection of which view elements to materialize in terms of storage space and view retrieval time. The selection of redundant views in a dependency hierarchy has been used for the pre-materialization of views in data cubes. A tree-based selection process has been utilized for selecting non-redundant wavelet packet bases for representing one-dimensional and two-dimensional digital signals. The process was extended to a graph that combines spatial segmentation and frequency decomposition for representing two-dimensional images.
In accordance with the aforementioned needs, it is an objective of the present invention to provide an apparatus and method for: generating representations of multidimensional data using view element sets, for adaptively and dynamically selecting representative view element sets according to patterns of view access, storage constraints and processing costs, and for assembling or synthesizing views of the data from view element sets.
It is another objective to provide a system and method having features for selecting and materializing view element sets according to storage costs and constraints, processing costs, and frequencies of view access by users.
Yet another objective is to provide a system and method having features for dynamically reconfiguring the data representation in accordance with the foregoing constraints and for adapting to emerging patterns of view access.
These and other objectives are realized by the present invention wherein an apparatus and method for generating a view element representation of multiple-attribute tabular data are provided, including converting tabular data into a multidimensional lattice form whereby each functional attribute of the relational data is mapped to a dimension in the lattice, and each cell in the lattice corresponds to an aggregation over records in the data table.
The invention further provides an apparatus and method for generating a view element representation of multidimensional lattice data comprising decomposing the multidimensional data into view elements such that the view elements retain sufficient information to reconstruct the original lattice data.
Alternatively, the invention provides for generating a view element data representation including iterative decomposition of the lattice data into aggregated and residual view elements or by spatially partitioning the lattice data.
Further taught are an apparatus and method for generating a view element data representation including the decomposition of the lattice data by iteratively and jointly aggregating and spatially partitioning the lattice data.
Under the inventive system for representing the data using view element sets, costs and benefits are assigned to the view elements and the view element sets are formed on the bases of the costs and benefits. A view of the data from a set of view elements is synthesized by selecting view elements from the view element sets and assembling the view elements together to construct the views.